/**
 * 
 */
package com.gragra.sampling.nonproj.structures.nonprojective.singleroot;
import java.util.Arrays;
import java.util.BitSet;
import java.util.concurrent.ConcurrentLinkedQueue;
import com.gragra.sampling.PopulationProbabilityAssigner;
import com.gragra.sampling.ThreadedUniformAccess;
import com.gragra.sampling.binary.ConvertSample;
import com.gragra.sampling.nonproj.ProposalDependencyAssigner;
import com.gragra.sampling.sequentialStructure.WordAndTagHolder;
/**
 * @author Christoph Teichmann
 * 16.10.2013
 */
public class GreedySingleRootNonProj extends
		GibbsGibbsSingleRootNonProjDepdTree
{
	/**
	 * @param wth
	 * @param threads
	 * @param cs
	 */
	public GreedySingleRootNonProj(WordAndTagHolder wth, int threads,
			ConvertSample cs)
	{super(wth, threads, cs);}
	/* (non-Javadoc)
	 * @see com.gragra.sampling.nonproj.structures.nonprojective.singleroot.GibbsGibbsSingleRootNonProjDepdTree#resampleRoot(com.gragra.sampling.PopulationProbabilityAssigner, double, int, com.gragra.sampling.ThreadedUniformAccess)
	 */
	@Override
	protected void resampleRoot(PopulationProbabilityAssigner pa,
			double annealing, int thread, ThreadedUniformAccess tua)
	{this.greedySamplingForPosition(pa, annealing, thread, tua);}
	/**
	 * 
	 * @param pos
	 * @param pa
	 * @param annealing
	 * @param thread
	 * @param tua
	 * @throws IllegalStateException
	 */
	protected void greedySamplingForPosition(PopulationProbabilityAssigner pa, double annealing, int thread,
			ThreadedUniformAccess tua) throws IllegalStateException
	{
		double oldProb = this.makeLogProbForThisConsideringAnnealing(pa, annealing, thread);
		double correction = 0.0;
		ProposalDependencyAssigner pda = (ProposalDependencyAssigner) pa;
		int[] storage = this.writeToStorage(thread);
		this.clear(thread);
		int[] shuffling = this.produceShuffle(thread, tua);
		for(int i=0;i<shuffling.length && shuffling[i] != -1;++i)
		{
			int toAssign = shuffling[i];
			BitSet candidates = this.makeAllHeadCandidates(toAssign, thread, pa);
			double[] probs = makeProbs(toAssign, candidates, annealing, pda, thread);
			correction += Math.log(probs[storage[toAssign]]);
			this.attachSingleFromStorage(toAssign, storage, thread);
			returnProbs(probs);
		}
		this.clear(thread);
		for(int i=0;i<shuffling.length && shuffling[i] != -1;++i)
		{
			int toAssign = shuffling[i];
			BitSet candidates = this.makeAllHeadCandidates(toAssign, thread, pa);
			double[] probs = makeProbs(toAssign, candidates, annealing, pda, thread);
			int choice = -1;
			double border = tua.nextDouble(thread);
			for(int head=candidates.nextSetBit(0);head>=0;head=candidates.nextSetBit(head+1))
			{
				border -= probs[head];
				if(border <= 0.0)
				{
					choice = head;
					break;
				}
			}
			if(choice < 0)
			{throw new IllegalStateException("Probabilities did not sum to one.");}
			this.attach(toAssign, choice, thread);
			correction -= Math.log(probs[choice]);
			returnProbs(probs);
		}
		returnShuffleToPool(shuffling);
		double newProb = this.makeLogProbForThisConsideringAnnealing(pa, annealing, thread);
		if(Math.log(tua.nextDouble(thread)) > newProb-oldProb+correction)
		{this.restore(storage, thread);}
		else
		{returnStorage(storage);}
	}
	/**
	 * 
	 * @param probs
	 */
	private void returnProbs(double[] probs)
	{probStore.add(probs);}
	/**
	 * 
	 * @param storage
	 */
	private void returnStorage(int[] storage)
	{storages.add(storage);}
	/**
	 * 
	 * @param toAssign
	 * @param storage
	 * @param thread
	 */
	private void attachSingleFromStorage(int toAssign, int[] storage, int thread)
	{this.attach(toAssign, storage[toAssign], thread);}
	/**
	 * 
	 * @param shuffling
	 */
	private void returnShuffleToPool(int[] shuffling)
	{shuffleBoard.add(shuffling);}
	/**
	 * 
	 * @param storage 
	 * @param thread
	 */
	private void restore(int[] storage, int thread)
	{
		for(int i=0;i<this.getLength();++i)
		{this.setNewHead(i, storage[i], thread);}
		this.returnStorage(storage);
	}
	/**
	 * 
	 */
	private final static ConcurrentLinkedQueue<double[]> probStore = new ConcurrentLinkedQueue<double[]>();
	/**
	 * 
	 * @param toAssign
	 * @param candidates
	 * @param annealing
	 * @param pda
	 * @param thread
	 * @return
	 */
	private double[] makeProbs(int toAssign, BitSet candidates,
			double annealing, ProposalDependencyAssigner pda, int thread)
	{
		double[] probs = probStore.poll();
		if(probs == null || probs.length < this.getLength()+1)
		{probs = new double[this.getLength()+1];}
		double max = Double.NEGATIVE_INFINITY;
		for(int head = candidates.nextSetBit(0);head>=0;head=candidates.nextSetBit(head+1))
		{
			this.attach(toAssign, head, thread);
			max = Math.max(max, probs[head] = pda.makeProposalLogProb(toAssign, head, this, thread)*annealing);
			this.detach(toAssign, thread);
		}
		double sum = 0.0;
		for(int head = candidates.nextSetBit(0);head>=0;head=candidates.nextSetBit(head+1))
		{sum += probs[head] = Math.exp(probs[head]-max);}
		for(int head = candidates.nextSetBit(0);head>=0;head=candidates.nextSetBit(head+1))
		{probs[head] /= sum;}
		return probs;
	}
	/**
	 * 
	 * @param thread
	 * @param tua
	 * @return
	 */
	private int[] produceShuffle(int thread,
			ThreadedUniformAccess tua)
	{
		int[] shuffle = shuffleBoard.poll();
		if(shuffle == null || shuffle.length < this.getLength())
		{shuffle = new int[this.getLength()];}
		Arrays.fill(shuffle, -1);
		int lenMin = this.getLength()-1;
		for(int i=0;i<this.getLength();++i)
		{shuffle[i] = i;}
		for(int i=0;i<this.getLength();++i)
		{
			int inter = shuffle[i];
			int next = tua.nextInt(thread,0,lenMin);
			shuffle[i] = shuffle[next];
			shuffle[next] = inter;
		}
		return shuffle;
	}
	/**
	 * 
	 */
	private final static ConcurrentLinkedQueue<int[]> shuffleBoard = new ConcurrentLinkedQueue<int[]>();
	/**
	 * 
	 * @param thread
	 */
	protected void clear(int thread)
	{
		for(int i=0;i<this.getLength();++i)
		{this.detach(i, thread);}
	}
	/**
	 * 
	 * @param thread
	 * @return 
	 */
	private int[] writeToStorage(int thread)
	{
		int[] store = storages.poll();
		if(store == null || store.length < this.getLength())
		{store = new int[this.getLength()];}
		for(int i=0;i<this.getLength();++i)
		{store[i] = this.getHeadPosition(i, thread);}
		return store;
	}
	/**
	 * 
	 */
	private final static ConcurrentLinkedQueue<int[]> storages = new ConcurrentLinkedQueue<int[]>();
}